package com.zjj.algorithm.learning.atguigu.algorithm;

import java.util.*;

/**
 * 使用 Prime 算法创建最小生成树
 *
 * @author zjj_admin
 * @date 2022/12/31 16:18
 */
public class PrimeAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = new int[][]{
                {-1, 5, 7, -1, -1, -1, 2},
                {5, -1, -1, 9, -1, -1, 3},
                {7, -1, -1, -1, 8, -1, -1},
                {-1, 9, -1, -1, -1, 4, -1},
                {-1, -1, 8, -1, -1, 5, 4},
                {-1, -1, -1, 4, 5, -1, 6},
                {2, 3, -1, -1, 4, 6, -1}
        };
        int vertex = data.length;
        //创建一个图对象
        Graph graph = new Graph(vertex);
        //创建一个最小生成树对象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, vertex, data, weight);
        //显示图
        minTree.showGraph(graph);

        Map<String, Object> res = minTree.prime(graph, 0);
        List<String> paths = (List<String>) res.get("paths");
        Integer shortestPath = (Integer) res.get("shortestPath");
        System.out.println("shortestPath = " + shortestPath);
        System.out.println("paths = " + paths);
    }
}




